#include "parsing.h"
#include "ui_parsing.h"
#include <iostream>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <fstream>
#include <QString>
#include <QFile>
#include <QTextStream>
#include <fstream>
#include <QFileDialog>
#include <QMessageBox>
#include <QGraphicsScene>
#include <QGraphicsView>
#include <QGraphicsItem>
#include <QPainterPath>
#include <QMap>

using namespace std;
parsing::parsing(QWidget *parent)
    : QWidget(parent), ui(new Ui::parsing)
{
    ui->setupUi(this);
}

parsing::~parsing()
{
    delete ui;
}

int stateCounter = 0;       // 状态数
int DFANodeCounter = 0;     // DFA 节点数量
int SimplifyDFACounter = 0; // 简化后DFA节点数量

map<char, int> priorityMap; // 设置正规式中符号的优先级
set<char> operatorChar;     // 当前正规式中所使用到的符号
set<char> operatorCharTmp;  // 当前正规式中暂时使用到的符号以及空符号#等

// 定义NFA的节点
struct State
{
    int id;
    vector<pair<char, State *>> transitions;
    // State* 指向另一个 State 对象，代表状态转移后的目标状态
    // 可能有潜在的问题 因为NFA节点可以状态转换不唯一 一对多
    // 如果用 vector<pair<char, State*>> transitions表示转换函数则会发生相同映射的覆盖
    bool isAccepting; // 是否终态
    bool isStarting;  // 是否起点
    State()
    {
        isAccepting = false;
        isStarting = false;
    }
};
// 定义NFA图的数据结构
struct NFA
{
    State *start;
    State *end;
};

// 定义 DFA 结点 每个节点存了其下一个状态节点以及当前id等信息
// 故在NFA的数据结构中只需要知道开始节点与结束节点即可
struct DFANode
{
    int id;
    vector<pair<char, DFANode *>> transitions;
    set<int> nfaNodes; // 这里的的DFA节点是由 NFA节点集合 得到的 NFA节点的数据结构是state
                       // 以id作为主键 故使用INT作为set的数据类型 当然也可以考虑使用state作为set的参数
    bool isAccepting;  // 是否终态 若一个DFA结点包含一个终态的NFA结点，则该DFA结点为终态
    bool isStarting;   // 起点
    int SDFANum;       // 化简后所属的  SDFA 结点

    DFANode()
    {
        isAccepting = false;
        isStarting = false;
        id = DFANodeCounter;
        DFANodeCounter++;
    }
};

// 简化后的 DFA 结点  DFA的最小化最终得到的节点是一个或者多个节点等价合并类
struct SimplifyDFANode
{
    int id;
    vector<pair<char, SimplifyDFANode *>> transitions;
    set<DFANode *> dfaNodes; // 这里的简化后的DFA节点是由 DFA节点集合 得到的
    bool isAccepting;
    bool isStarting;

    SimplifyDFANode(int counter, bool isAc = false)
    {
        id = counter;
        isAccepting = isAc;
        isStarting = false; // 起点的初始化赋值不在构造函数 只有最简化DFA的节点可以进行结束态的始化构造赋值
    }
};

// 分别创建一维DFA节点集合 二维NFA节点集合(NFA的状态转换函数，可以实现同一个状态转到不同的状态)
// 二维DFA节点集合  二维最小化DFA节点集合  出度与入度 存储NFA DFA映射的map 最小化DFA节点队列
int outDegree[1000];
int inDegree[1000];

vector<State *> G[1000]; // 类似邻接表 一个数组单元[]存储NFA的节点信息 transition中相当于存储了输入字符 即边的信息
vector<DFANode *> DFAG[1000];
vector<SimplifyDFANode *> SDFAG[1000];

vector<DFANode *> dfaNodes;          // 能保存dfa节点
map<int, State *> NFAMap;            // 新添加NFA节点时改动的数据结构 包含节点State->id与State
map<int, SimplifyDFANode *> SDFAMap; // 新添加SimplifyDFA节点时改动的数据结构


// 整理成输出格式
string nfaTable[1000][1000];
string dfaTable[1000][1000];
string sdfaTable[1000][1000];

// 在文件开头添加比较函数
struct EdgeKey
{
    QPointF start;
    QPointF end;

    bool operator<(const EdgeKey &other) const
    {
        if (start.x() != other.start.x())
            return start.x() < other.start.x();
        if (start.y() != other.start.y())
            return start.y() < other.start.y();
        if (end.x() != other.end.x())
            return end.x() < other.end.x();
        return end.y() < other.end.y();
    }
};

// 是否为变量
bool isWordChar(char c)
{
    if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))
        return true;
    return false;
}

// 创建一个新的NFA节点
State *createState(int id, bool isAccepting = false)
{
    State *newState = new State;
    newState->id = id;
    newState->isAccepting = isAccepting;
    NFAMap.insert(make_pair(id, newState));
    return newState;
}

// 像这些为NFA图添加的链接 选择 星闭包 ＋闭包等操作都是基于空闭包的 故不需要改变出度与入度
// 而非空闭包的点需要改变出度与入度
// 执行NFA图的连接操作 ab == nfa1.start--ε-->nfa1.end--nfa2.start--ε-->nfa2.end
// 连接操作的本质是：将nfa1的终态与nfa2的初态连接起来 并更新出度与入度 不会有新的终态与初态
NFA concatenate(NFA nfa1, NFA nfa2)
{
    // 将 NFA 2 的起始状态加入到 NFA 1 的终态状态的 pair(#, NFA) 并且删除相应的终态与初态的关系
    // # 在这里代表的是一个 空输入符号，通常在 NFA 中用于表示 epsilon 转移（ε-转移），即不消耗任何输入符号的转移
    //  是 NFA 内部的数据更新，处理实际的状态转移
    nfa1.end->transitions.push_back(make_pair('#', nfa2.start));
    nfa1.end->isAccepting = false;
    nfa2.start->isStarting = false;
    // 将 G 中每一个数组下标作为一个NFA状态id 将状态转换信息同时存储到G中
    // 负责 在状态图 G 中维护状态之间的连接关系。它是在一个外部数据结构中，记录每个状态的出发点和连接目标
    // 这个图结构通常用于后续的算法，例如确定化或最小化时，快速查找某个状态可以跳转到哪些其他状态
    G[nfa1.end->id].push_back(nfa2.start);
    return {nfa1.start, nfa2.end};
}

// 执行NFA图的选择操作
//                  nfa1.start -- nfa1.end
//  newStart + ε +                           + ε + newEnd
//                  nfa2.start -- nfa2.end
NFA unionNFA(NFA nfa1, NFA nfa2)
{
    // 以新建的state作为起点连接两个NFA
    // vector<pair<char, State*>> transitions
    // vector<State*> G[] G 不需要知道是哪个符号转来的 只需要将NFA的stateid这一行添加新状态转换的映射即可
    State *newStart = createState(stateCounter++);
    newStart->isStarting = true;
    // # 在这里代表的是一个 空输入符号，通常在 NFA 中用于表示 epsilon 转移（ε-转移），即不消耗任何输入符转移
    // map支持一对一 加上vector就可以一对多了 如果在后期进行计算闭包或者画图 可以使用其他的实现一对多 且在使用时不发生冲突的数据结构
    newStart->transitions.push_back(make_pair('#', nfa1.start));
    newStart->transitions.push_back(make_pair('#', nfa2.start));
    G[newStart->id].push_back(nfa1.start);
    G[newStart->id].push_back(nfa2.start);
    nfa1.start->isStarting = false;
    nfa2.start->isStarting = false;

    // 毕竟都是空 加多少状态都无影响 只是最后分析时方便
    State *newEnd = createState(stateCounter++, true);
    nfa1.end->transitions.push_back(make_pair('#', newEnd));
    nfa2.end->transitions.push_back(make_pair('#', newEnd));
    G[nfa1.end->id].push_back(newEnd);
    G[nfa2.end->id].push_back(newEnd);
    nfa1.end->isAccepting = false;
    nfa2.end->isAccepting = false;

    return {newStart, newEnd};
}

// 执行NFA图的闭包操作 对象肯定是一个NFA
//    newStart + ε + nfa.start---nfa.end + ε + newEnd
//
//    newStart + ε + newEnd
NFA closure(NFA nfa)
{
    State *newStart = createState(stateCounter++);
    newStart->isStarting = true;
    newStart->transitions.push_back(make_pair('#', nfa.start));
    G[newStart->id].push_back(nfa.start);
    nfa.start->isStarting = false;

    State *newEnd = createState(stateCounter++, true); // newEnd的isAccepting已经在构造函数中声明
    nfa.end->transitions.push_back(make_pair('#', newEnd));
    G[nfa.end->id].push_back(newEnd);
    nfa.end->isAccepting = false;

    // 产生*闭包 即从newStart开始 因为从其开始第一个必经过ε
    nfa.end->transitions.push_back(make_pair('#', newStart));
    G[nfa.end->id].push_back(newStart);

    // 绕路走零环 直接到newEnd
    newStart->transitions.push_back(make_pair('#', newEnd));
    G[newStart->id].push_back(newEnd);

    return {newStart, newEnd};
}

// 执行NFA图的正闭包操作  对象肯定是一个NFA
//  newStart + ε + nfa.start---nfa.end + ε + newEnd
NFA closurePostive(NFA nfa)
{

    State *newStart = createState(stateCounter++);
    newStart->isStarting = true;
    newStart->transitions.push_back(make_pair('#', nfa.start));
    G[newStart->id].push_back(nfa.start);
    nfa.start->isStarting = false;

    State *newEnd = createState(stateCounter++, true); // newEnd的isAccepting已经在构造函数中声明
    nfa.end->transitions.push_back(make_pair('#', newEnd));
    G[nfa.end->id].push_back(newEnd);
    nfa.end->isAccepting = false;

    // 产生正闭包 即从newStart开始 因为从其开始第一个必经过ε 故直接从nfa.start开始 相当于+闭包的操作
    nfa.end->transitions.push_back(make_pair('#', nfa.start));
    G[nfa.end->id].push_back(nfa.start);

    return {newStart, newEnd};
}

string intToString(int num)
{
    string result = "";
    if (num == 0)
    {
        return "0";
    }
    while (num > 0)
    {
        int digit = num % 10;
        char digitChar = '0' + digit;
        result = digitChar + result;
        num /= 10;
    }
    return result;
}

// 将正则表达式转换为NFA图
bool regexToNFA(string regex)
{
    stack<NFA> nfaStack;
    stack<char> operatorStack;
    stack<char> parenthesisStack;  // 用于检查括号匹配

    for (char c : regex)
    {
        if (c == '(')
        {
            operatorStack.push(c);  // 左括号入栈
            parenthesisStack.push(c);  // 记录左括号
        }
        else if (c == ')')
        {
            // 右括号，检查是否有左括号匹配
            if (parenthesisStack.empty()) return false;  // 如果没有左括号匹配，返回不合法
            parenthesisStack.pop();  // 匹配到左括号，弹出左括号

            // 处理运算符直到遇到左括号
            while (!operatorStack.empty() && operatorStack.top() != '(')
            {
                char op = operatorStack.top();
                operatorStack.pop();

                if (op == '|')
                {
                    if (nfaStack.size() < 2) return false;  // | 需要两个NFA
                    NFA nfa2 = nfaStack.top();
                    nfaStack.pop();
                    NFA nfa1 = nfaStack.top();
                    nfaStack.pop();
                    nfaStack.push(unionNFA(nfa1, nfa2));
                }
                else if (op == '.')
                {
                    if (nfaStack.size() < 2) return false;  // . 需要两个NFA
                    NFA nfa2 = nfaStack.top();
                    nfaStack.pop();
                    NFA nfa1 = nfaStack.top();
                    nfaStack.pop();
                    nfaStack.push(concatenate(nfa1, nfa2));
                }
                else if (op == '*')
                {
                    if (nfaStack.size() < 1) return false;  // * 需要一个NFA
                    NFA nfa1 = nfaStack.top();
                    nfaStack.pop();
                    nfaStack.push(closure(nfa1));
                }
                else if (op == '+')
                {
                    if (nfaStack.size() < 1) return false;  // + 需要一个NFA
                    NFA nfa1 = nfaStack.top();
                    nfaStack.pop();
                    nfaStack.push(closurePostive(nfa1));
                }
            }
            // 如果栈顶是左括号，匹配成功，弹出左括号
            if (operatorStack.empty() || operatorStack.top() != '(') return false;
            operatorStack.pop();  // 弹出左括号
        }
        else if (c == '*' || c == '+')
        {
            // 处理一元操作符 * 或 +
            if (nfaStack.size() < 1) return false;  // * 和 + 需要至少一个NFA
            NFA nfa1 = nfaStack.top();
            nfaStack.pop();
            if (c == '*')
                nfaStack.push(closure(nfa1));
            else
                nfaStack.push(closurePostive(nfa1));
        }
        else if ((c == '|' || c == '.') && !operatorStack.empty() && priorityMap[c] <= priorityMap[operatorStack.top()])
        {
            // 运算符优先级处理
            while (!operatorStack.empty() && priorityMap[c] <= priorityMap[operatorStack.top()] && operatorStack.top() != '(')
            {
                char op = operatorStack.top();
                operatorStack.pop();

                if (op == '|')
                {
                    if (nfaStack.size() < 2) return false;  // | 需要两个NFA
                    NFA nfa2 = nfaStack.top();
                    nfaStack.pop();
                    NFA nfa1 = nfaStack.top();
                    nfaStack.pop();
                    nfaStack.push(unionNFA(nfa1, nfa2));
                }
                else if (op == '.')
                {
                    if (nfaStack.size() < 2) return false;  // . 需要两个NFA
                    NFA nfa2 = nfaStack.top();
                    nfaStack.pop();
                    NFA nfa1 = nfaStack.top();
                    nfaStack.pop();
                    nfaStack.push(concatenate(nfa1, nfa2));
                }
            }
            operatorStack.push(c);  // 当前操作符入栈
        }
        else if (c == '|' || c == '.')
        {
            operatorStack.push(c);
        }
        else
        {
            // 处理普通字符：构造新的NFA
            State *state1 = createState(stateCounter++);
            state1->isStarting = true;
            State *state2 = createState(stateCounter++, true);
            state1->transitions.push_back(make_pair(c, state2));
            operatorChar.insert(c);
            G[state1->id].push_back(state2);

            outDegree[state1->id]--;
            inDegree[state2->id]--;
            nfaStack.push({state1, state2});
        }
    }

    // 检查是否有未匹配的左括号
    if (!parenthesisStack.empty()) return false;

    // 处理剩余的操作符
    while (!operatorStack.empty())
    {
        char op = operatorStack.top();
        operatorStack.pop();

        if (op == '|')
        {
            if (nfaStack.size() < 2) return false;  // | 需要两个NFA
            NFA nfa2 = nfaStack.top();
            nfaStack.pop();
            NFA nfa1 = nfaStack.top();
            nfaStack.pop();
            nfaStack.push(unionNFA(nfa1, nfa2));
        }
        else if (op == '.')
        {
            if (nfaStack.size() < 2) return false;  // . 需要两个NFA
            NFA nfa2 = nfaStack.top();
            nfaStack.pop();
            NFA nfa1 = nfaStack.top();
            nfaStack.pop();
            nfaStack.push(concatenate(nfa1, nfa2));
        }
    }

    // 确保最终栈中只有一个NFA
    if (nfaStack.size() != 1) return false;

    return true;
}

//`NFAtoDFA` 函数实现了非确定性有限自动机（NFA）到确定性有限自动机（DFA）的转换过程，并通过一系列对dfanodes的操作，如DFA转换的nfanodes已经在前面计算好，每一列可以直接用DFA所包含的nfanodes进行输出，不需要再从初态的空闭包开始计算，其确保了转换后的DFA符合严格的规范。首先，函数遍历所有NFA状态，创建相应的DFA节点，并使用深度优先搜索（DFS）找出每个DFA节点所对应的所有NFA状态。这些状态存储在DFA节点的 `nfaNodes` 集合中，确保了DFA节点对NFA状态的唯一表示，dfsFindDFA是在找到的dfaNodes[]的nfaNodes字段的终点Id(肯定是因为没有空闭包所以跳出dfs的)的邻接点node->transitions中继续找直到没有空闭包跳出，这次的nfaNodes字段使用nfaSet来代替，因为只是为了与之前得到的每一个dfaNodes[]->nfaNodes对比，相同的话得到当前节点(一定不是空闭包)所有非空可达点的nfaNodes相契合，即两个DFA可以联通保存到dfas中循环遍历所有的dfaNode->nfaNodes每次都返回给nextNode，opDfaMap存储所有nextNode，只要找到相同的转换符号，就将找到的之前最开始保存在opDfaMap中的DFA与当前又发现的新的DFA存储在unionPair中，注意opdfamap的位置，一次NFA循环下的nextnode相不相同无所谓，不同就分别存到opdfamap，相同则也肯定是一个起点nfa出发的(使用findNextDFANode产生的nextnode)相同转换符号。将每一个dfaNode->nfaNodes的元素(一般也就只是最后一个NFA节点，因为前面的节点都是空闭包得到的)findNextDFANode，即该模块实现的是将每一个相同DFA的终态NFA节点通过不同的转换符号得到的不同的DFA拼接起来。由于删除了一些冗余的DFA所以需要把重复的DFA进行erase，然后再对重新分配好序号的DFA通过dfsFindDFA更新nextNFAs，通过nextNFAs的操作符映射得到nextNode，如果找到一个DFA节点的NFA集合与当前操作符对应的NFA集合相同，则将该操作符和DFA节点的对应关系添加到nextNode中作为当前DFA节点的下一个DFA节点并存储转换符号。然后，函数合并了具有相同转换符号的DFA节点，避免了DFA中出现重复的转换符号。通过 `opDfaMap` 映射符号到DFA节点，若发现已有的DFA节点与新创建的DFA节点通过相同的转换符号关联，则将其合并为同一个DFA节点。这一步骤使用 `unionPair` 保存所有需要合并的节点对。合并后，函数重新排列DFA节点的ID，确保DFA节点ID从0开始并连续，注意之前的DFAmap映射到哪一个都可以，因为最后会把所有相同起点、相同转换符号的不同转换后的状态合并了，比如d1--a-->d2，d1--a-->d3，则需要将d2与d3合并。nfaNodes本身就是set不需要考虑合并后Id的重复问题，dfaNodes.erase(remove(dfaNodes.begin(), dfaNodes.end(), dfa2), dfaNodes.end());使用remove将需要删除的元素移动到容器的末尾，并使用erase在dfaNodes中删除这些冗余集合来实现DFA集合的合并，简化后续的状态管理与图形可视化。接着，函数遍历每个DFA节点的NFA节点，更新其转换关系，确保每个DFA节点的状态转移是确定性的。通过查找每个NFA节点的转换符号，并根据这些符号构建DFA的状态转移，确保每个状态通过唯一的转换符号转移到另一个状态。最后，函数打印出DFA的状态图，展示每个DFA节点的状态转换情况，并标明是否为接受状态。通过这些步骤，`NFAtoDFA` 实现了从NFA到DFA的高效转换，确保了自动机的确定性和状态转移的清晰性。
// 遍历 NFA 中的每个节点，并将相应的状态集添加到 DFA 的状态中
// dfs的作用是将所有非ε转换的NFA节点及其邻接点均添加到DFA节点中
// 后面的findNextDFANode函数的作用是：在已有DFA基础上 通过ε以及非ε转换 找到下一个DFA节点
void dfs(int node)
{
    // node 为NFA的节点id
    // DFA 的每个状态包含了一个或多个 NFA 状态 dfaNodes 存储了这些 DFA 状态的集合，而每个 DFA 状态对应一个 NFA 状态的集合（通过 nfaNodes 成员变量）
    // 一开始插入的全是node为起点的NFA编号 且在458行调用可知 每次都是新push的DFAnode 所以肯定在执行dfs时更新的节点是DFANodes中的最后一个DFANodes*
    dfaNodes[dfaNodes.size() - 1]->nfaNodes.insert(node);
    // dfs函数：只负责遍历起点到终态的所有NFA节点，并将它们标记为属于同一个DFA状态 并没有改动

    if (NFAMap[node]->isAccepting == true)
    {
        // 如果当前的 NFA 状态 node 是接受状态（终态），则将对应的 DFA 状态设置为接受状态
        dfaNodes[dfaNodes.size() - 1]->isAccepting = true; // 设置终态
    }
    if (NFAMap[node]->isStarting == true)
    {
        // 如果当的 NFA 状态是起始状态，则将对应的 DFA 状态置为起始状态
        dfaNodes[dfaNodes.size() - 1]->isStarting = true; // 设置初态
    }
    // 参考1167行开始执行代码 重点！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
    // 出度入度<=0的点均为非ε转换的点 因为我们要处理的是ε转换的点 故碰见出度入度<=0的点就返回
    if (outDegree[node] <= 0)
    {
        return; // 到达终态边缘点了
    }
    // 若当前NFA节点还有度就要dfs出度节点及其邻接点
    // 遍历下一个 由于G第二维是State类型 且为每个节点的邻接表 故容量上限设置为G[node].size()
    for (int i = 0; i < G[node].size(); i++)
    {
        dfs(G[node][i]->id); // 遍历了以node为节点的所有邻接点 并对所有邻接点进行dfs
        // NFA的邻接点只是将其id整合到DFA的nfaNodes属性中 以及设置初态终态 其他无改动
        // 表示从 NFA 状态 node 出发的所有邻接节点
    }
}

void dfsFindDFA(State *node, set<int> *nfaSet)
{
    // 把这个 NFA 结加入到新的 DFA 结点
    nfaSet->insert(node->id);
    if (outDegree[node->id] <= 0)
    {
        return; // 到达边缘点了
    }
    // 遍历下一个
    for (int i = 0; i < G[node->id].size(); i++)
    {
        dfsFindDFA(G[node->id][i], nfaSet);
    }
}

// 从dfs得到的ε闭包的终点找看是不是还能继续拓展 当前节点肯定不可能满足dfsFindDFA的if条件
// 肯定是dfsFindDFA(edge.second, &nfaSet); 即从终点的邻接点开始找
// 如果找到了一个相同的NFA状态集 则说明找到了一个DFA节点 并把这个DFA节点加入dfas
vector<pair<char, DFANode *>> findNextDFANode(State *node)
{
    // node是从非空入度转换符号的节点的ε闭包的State id
    vector<pair<char, DFANode *>> dfas;
    // 无连接节点
    if (node->transitions.size() == 0)
        return dfas;
    // 有邻接节点就把这个 NFA 结点加入到新的 DFA 结点
    for (auto edge : node->transitions)
    {
        set<int> nfaSet;
        // 当前的Node不可能再有空闭包了 只能是当前State的transitions才会有闭包
        dfsFindDFA(edge.second, &nfaSet);
        for (auto dfa : dfaNodes)
        {
            if (dfa->nfaNodes == nfaSet)
            {
                // 说明node可以通过edge.first转换到dfa 且edge.first是非空的！
                dfas.push_back(make_pair(edge.first, dfa));
            }
        }
    }
    return dfas;
}

void UnionDFA(DFANode *dfa1, DFANode *dfa2)
{
    if (dfa2->isAccepting)
        dfa1->isAccepting = true;
    if (dfa2->isStarting)
        dfa1->isStarting = true;
    for (auto nfa : dfa2->nfaNodes)
    {
        dfa1->nfaNodes.insert(nfa);
    }
    // 通过使用remove将需要删除的元素移动到容器的末尾，并使用erase删除这些元素来实现
    dfaNodes.erase(remove(dfaNodes.begin(), dfaNodes.end(), dfa2), dfaNodes.end());
}
// 首先将所有NFA节点的ε闭包找到并加入DFANodes
// 因为dfs已经把所有NFA的ε闭包加入到DFA节点的nfanodes属性中 故这里只需要找到非空节点进行拓展
void NFAtoDFA()
{
    // 计算每个 DFA 结点拥有哪些 NFA 结点
    for (int i = 0; i < stateCounter; i++)
    {
        // 条件成立时这个State节点是通过非ε转换到达的节点 即对于非空转换到达的节点进行dfs才有意义
        if (inDegree[i] <= 0)
        {
            DFANode *NewDFANode = new DFANode();
            // dfaNodes是在这里被初始化的
            dfaNodes.push_back(NewDFANode);
            // 对当前State节点进行dfs 并把所有经过空转换的State节点id加入到dfanode的nfanodes属性中
            dfs(i);
        }
    }
    // 上面的循环结束后得到的是以每个不含ε转换的NFA进行拓展的DFA节点 每个DFA节点均存储在dfanodes里了

    // 合并相同字母边指向的 DFA点
    vector<pair<DFANode *, DFANode *>> unionPair;
    for (int i = 0; i < dfaNodes.size(); i++)
    {
        DFANode *dfaNode = dfaNodes[i];
        // 记录所有NFA终态节点的转换符号与转换后的DFA节点
        map<char, DFANode *> opDfaMap;
        for (auto nfa : dfaNode->nfaNodes)
        {
            // 类似链表 可以理解成一个状态只有一个出度与入度 出度>0说明转换函数的符号是ε
            // 因为之前dfs已经使用同样的方式处理过空闭包
            // 这里一旦处理的NFA节点的transition是ε则跳过处理 直到遇到非ε转换
            if (outDegree[nfa] > 0)
                // 跳过中间所有的ε转换节点 这里应该是only终点可以跳过此if语句
                // 因为终点是dfs的跳出条件 故会保留
                continue;
            // 处理终点 NFAMap(id,state*)储存dfs的映射结果
            // nextNode是一个尾NFA经过非ε可达点转换得到的当前NFAMap[nfa]所在DFA的非空转换NFA
            vector<pair<char, DFANode *>> nextNode = findNextDFANode(NFAMap[nfa]);
            if (nextNode.empty())
            {
                continue;
            }
            // 一次NFA循环下的nextnode相不相同无所谓 不同就分别存到opdfamap
            // 相同则也肯定是一个起点出发的相同转换符号
            for (int j = 0; j < nextNode.size(); j++)
            {
                // 如果当前转换符号在opDfaMap中已经存在
                // 则说明对于相同的转换函数 同一起点已经在一个DFA节点 则需要将新得到的DFA节点与其合并
                // d1--a-->d2
                // d1--a-->d3
                // 则需要将d2与d3合并  因为一般是按照前面所设置的规定进行操作 故不太可能出现这种情况
                // find的返回值是迭代器 如果没找到则返回end()
                if (opDfaMap.find(nextNode[j].first) != opDfaMap.end())
                {
                    DFANode *oldDfa = opDfaMap[nextNode[j].first];
                    unionPair.push_back(make_pair(oldDfa, nextNode[j].second));
                }
                // 如果当前转换符号在opDfaMap中不存在 则说明还没有一个DFA节点 则需要创建
                opDfaMap.insert(make_pair(nextNode[j].first, nextNode[j].second));
            }
        }
    }
    // 因为DFA不可以有多个相同的符号指向 故存在这种情况就要进行union
    for (int i = 0; i < unionPair.size(); i++)
    {
        UnionDFA(unionPair[i].first, unionPair[i].second);
    }

    DFANodeCounter = dfaNodes.size();
    // 使DFA节点 ID 连续且从0开始编号
    for (int i = 0; i < dfaNodes.size(); i++)
    {
        if (i != dfaNodes[i]->id)
        {
            int oldId = dfaNodes[i]->id;
            int newId = i;
            dfaNodes[i]->id = newId;
        }
    }

    // 连接 DFA
    for (int i = 0; i < DFANodeCounter; i++)
    {
        DFANode *dfaNode = dfaNodes[i];
        vector<pair<char, DFANode *>> nextNode;
        map<char, set<int>> nextNFAs;
        // 初始化nextNFAs 只是为了插入转换符号而设置的tmp
        for (auto op : operatorChar)
        {
            set<int> tmp;
            nextNFAs.insert(make_pair(op, tmp));
        }
        // 从新处理重新分配序号的DFA
        // 这些nfa都是非空转换节点
        for (auto nfa : dfaNode->nfaNodes)
        {                           // 遍历每一个结点
            if (outDegree[nfa] > 0) // 含有ε闭包跳过
                continue;
            if (NFAMap[nfa]->transitions.size() == 0) // 当前节点为终态 不可转换
                continue;

            char op = NFAMap[nfa]->transitions[0].first;
            // 这里赋值给nfaset的原因是可能存在多个相同的转换符号 故需要将所有相同的转换符号的NFA节点集合起来
            set<int> nfaSet = nextNFAs[op];
            dfsFindDFA(NFAMap[nfa]->transitions[0].second, &nfaSet);

            nextNFAs[op] = nfaSet;
        }
        // 对于每个DFA节点 前面nextNFAs已经得到所有非空转换DFA的NFA节点 现在需要找到对应的DFA节点
        for (auto op : operatorChar)
        {
            set<int> nfaSet = nextNFAs[op];
            if (nfaSet.empty())
                continue;
            for (auto dfa : dfaNodes)
            {
                if (dfa->nfaNodes == nfaSet)
                {
                    nextNode.push_back(make_pair(op, dfa));
                }
            }
        }

        for (int j = 0; j < nextNode.size(); j++)
        {
            // 现在需要更新的是DFA的transitions以及DFAG
            dfaNode->transitions.push_back(make_pair(nextNode[j].first, nextNode[j].second));
            DFAG[dfaNode->id].push_back(nextNode[j].second);
        }
    }

    for (int i = 0; i < DFANodeCounter; i++)
    {
        cout << i << " : ";
        for (int j = 0; j < DFAG[i].size(); j++)
        {
            cout << DFAG[i][j]->id << DFAG[i][j]->isAccepting << " ";
        }
        cout << endl;
    }
    cout << " ------  DFA图结束 ---------" << endl;
}

// 每个符号对应的转换后状态与原始状态集关联起来
vector<SimplifyDFANode *> SplitDFANode(SimplifyDFANode *node, char op) {
    vector<SimplifyDFANode*> result;
    map<int, set<DFANode*>> splitGroups;  // 用组号来映射该组包含的DFA节点

    // 遍历当前节点包含的所有DFA节点
    for (auto dfanode : node->dfaNodes) {
        int targetGroup = -1;  // 默认为-1表示没有转换
        
        // 查找该节点通过op转换后的目标状态所在的组
        for (auto& trans : dfanode->transitions) {
            if (trans.first == op) {
                targetGroup = trans.second->SDFANum;  // 化简后转换后的DFA所属SDFA节点
                break;  // DFA每个输入只有一个转换
            }
        }
        
        // 将当前状态加入到对应的组
        splitGroups[targetGroup].insert(dfanode);
    }

    // 为每个分组创建新的SimplifyDFANode
    bool isFirst = true;
    for (auto& group : splitGroups) {
        SimplifyDFANode* newNode;
        if (isFirst) {
            // 第一个分组保持原有ID
            newNode = new SimplifyDFANode(node->id);
            isFirst = false;
        } else {
            newNode = new SimplifyDFANode(SimplifyDFACounter++);
        }

        // 设置新节点的属性
        newNode->dfaNodes = group.second;
        
        // 检查分组中的状态属性
        for (auto dfa : group.second) {
            if (dfa->isAccepting) {
                newNode->isAccepting = true;
            }
            if (dfa->isStarting) {
                newNode->isStarting = true;
            }
        }
        
        result.push_back(newNode);
    }

    return result;
}

void SimplifyDFA() {
    // 初始化：将所有状态分为终态和非终态两组
    set<DFANode*> acceptStates;
    set<DFANode*> nonAcceptStates;
    SimplifyDFACounter = 0;

    // 第一次划分：按照终态和非终态
    for (auto& dfaNode : dfaNodes) {
        if (dfaNode->isAccepting) {
            acceptStates.insert(dfaNode);
        } else {
            nonAcceptStates.insert(dfaNode);
        }
    }

    // 创建初始的SimplifyDFA节点
    vector<SimplifyDFANode*> currentGroups;
    
    if (!nonAcceptStates.empty()) {
        SimplifyDFANode* nonAcceptGroup = new SimplifyDFANode(SimplifyDFACounter++);
        nonAcceptGroup->dfaNodes = nonAcceptStates;
        for (auto dfa : nonAcceptStates) {
            if (dfa->isStarting) nonAcceptGroup->isStarting = true;
        }
        currentGroups.push_back(nonAcceptGroup);
        SDFAMap[nonAcceptGroup->id] = nonAcceptGroup;
    }
    
    if (!acceptStates.empty()) {
        SimplifyDFANode* acceptGroup = new SimplifyDFANode(SimplifyDFACounter++, true);
        acceptGroup->dfaNodes = acceptStates;
        for (auto dfa : acceptStates) {
            if (dfa->isStarting) acceptGroup->isStarting = true;
        }
        currentGroups.push_back(acceptGroup);
        SDFAMap[acceptGroup->id] = acceptGroup;
    }

    bool changed;
    do {
        changed = false;
        vector<SimplifyDFANode*> newGroups;
        
        // 对每个当前的组进行处理
        for (auto group : currentGroups) {
            // 对每个输入符号进行检查
            for (auto op : operatorChar) {
                // 尝试对当前组进行分割
                vector<SimplifyDFANode*> splitResult = SplitDFANode(group, op);
                
                // 如果分割后的组数大于1，说明需要继续划分
                if (splitResult.size() > 1) {
                    changed = true;
                    // 从当前组中移除这些状态
                    auto it = find(currentGroups.begin(), currentGroups.end(), group);
                    if (it != currentGroups.end()) {
                        currentGroups.erase(it);
                    }
                    // 添加新的组
                    for (auto newGroup : splitResult) {
                        currentGroups.push_back(newGroup);
                        SDFAMap[newGroup->id] = newGroup;
                        // 更新每个DFA节点所属的组号
                        for (auto dfa : newGroup->dfaNodes) {
                            dfa->SDFANum = newGroup->id;
                        }
                    }
                    break;  // 找到一个可以分割的输入符号就退出
                }
            }
            if (changed) break;  // 如果发生了变化，重新开始检查所有组
        }
    } while (changed);

    // 清理旧的映射关系
    SDFAMap.clear();
    
    // 重新编号并建立新的映射关系
    SimplifyDFACounter = 0;
    for (auto group : currentGroups) {
        group->id = SimplifyDFACounter++;
        SDFAMap[group->id] = group;
        // 更新DFA节点的组号
        for (auto dfa : group->dfaNodes) {
            dfa->SDFANum = group->id;
        }
    }
}

void BuildSimplifyDFA()
{
    // 处理每个SDFA节点的每一个DFANodes的每一个transitions
    for (auto sdfa : SDFAMap)
    {
        for (auto dfa : sdfa.second->dfaNodes)
        {
            for (auto nextNode : dfa->transitions)
            {
                char op = nextNode.first;
                int nextSdfa = nextNode.second->SDFANum;
                bool hasAdd = false;
                // 检查是否已经存在相同的SDFA转换
                for (int i = 0; i < sdfa.second->transitions.size(); i++)
                {
                    if (sdfa.second->transitions[i].first == op && sdfa.second->transitions[i].second->id == nextSdfa)
                        hasAdd = true;
                }
                // 设置SDFA的transitions
                if (!hasAdd)
                {
                    sdfa.second->transitions.push_back(make_pair(op, SDFAMap[nextSdfa]));
                    SDFAG[sdfa.first].push_back(SDFAMap[nextSdfa]);
                }
            }
        }
    }

    for (int i = 0; i < SimplifyDFACounter; i++)
    {
        cout << i << " : ";
        for (auto pr : SDFAMap[i]->transitions)
        {
            cout << pr.first << " " << pr.second->id << " ";
        }
        cout << endl;
    }
    cout << " ----------  上面是简化后的 DFA -----------" << endl;
}

void DisplayNFA()
{
    operatorCharTmp = operatorChar;
    operatorCharTmp.insert('#');
    // 行
    int rowNum = stateCounter;
    // 列 要加上初态终态一列 以及stateCounter一列
    int colNum = operatorCharTmp.size() + 2;
    for (auto nfa : NFAMap)
    {
        int num = nfa.first;
        nfaTable[num][1] = intToString(num);
        State *nfaNode = nfa.second;

        // 处理初态和终态
        if (nfaNode->isStarting)
            nfaTable[num][0] = "start";
        if (nfaNode->isAccepting)
            nfaTable[num][0] = "end";

        int col = 2; // 从第二列开始，处理每个操作符

        // 遍历 operatorCharTmp 中的每个操作符
        for (auto op : operatorCharTmp)
        {
            for (int i = 0; i < nfaNode->transitions.size(); i++)
            {
                if (nfaNode->transitions[i].first == op)
                {
                    nfaTable[num][col] += intToString(nfaNode->transitions[i].second->id);
                    nfaTable[num][col] += ","; // 在每个状态后加逗号
                }
            }
            col++;
        }

        // 移除每列的最后一个逗号
        col = 2;
        for (auto op : operatorCharTmp)
        {
            if (nfaTable[num][col].size() > 0)
            {
                nfaTable[num][col].pop_back(); // 去掉最后一个逗号
            }
            col++;
        }
    }

    for (int i = 0; i < rowNum; i++)
    {
        for (int j = 0; j < colNum; j++)
        {
            if (nfaTable[i][j] == "")
                nfaTable[i][j] = " ";
        }
    }

    cout << "     ";
    for (auto op : operatorCharTmp)
    {
        cout << op << " ";
    }
    cout << endl;
    for (int i = 0; i < rowNum; i++)
    {
        for (int j = 0; j < colNum; j++)
        {
            cout << nfaTable[i][j] << " ";
        }
        cout << endl;
    }
}

bool cmp(DFANode *node1, DFANode *node2)
{
    return node1->id < node2->id;
}

string getAllNfaFromDFANode(DFANode *dfaNode)
{
    string ans = "{ ";
    for (auto nfaNum : dfaNode->nfaNodes)
    {
        ans += intToString(nfaNum);
        ans += ",";
    }
    ans[ans.size() - 1] = '}';
    return ans;
}

void DisplayDFA()
{
    cout << "------ 测试 ----------" << endl;
    int rowNum = DFANodeCounter;
    int colNum = operatorChar.size() + 2;
    sort(dfaNodes.begin(), dfaNodes.end(), cmp);
    for (int i = 0; i < dfaNodes.size(); i++)
    {
        DFANode *dfa = dfaNodes[i];
        cout << i << " : ";
        //
        dfaTable[i][1] = getAllNfaFromDFANode(dfa);
        if (dfa->isAccepting)
            dfaTable[i][0] = "end";
        if (dfa->isStarting)
            dfaTable[i][0] += "start";
        int col = 2;
        for (auto op : operatorChar)
        {
            for (int j = 0; j < dfa->transitions.size(); j++)
            {
                if (dfa->transitions[j].first == op)
                {
                    cout << dfa->transitions[j].first << dfa->transitions[j].second->id << " ";
                    dfaTable[i][col] = getAllNfaFromDFANode(dfa->transitions[j].second);
                }
            }
            col++;
        }
        cout << endl;
    }

    for (int i = 0; i < rowNum; i++)
    {
        for (int j = 0; j < colNum; j++)
        {
            if (nfaTable[i][j] == "")
                nfaTable[i][j] = "-----------";
        }
    }

    cout << "-------------";
    for (auto op : operatorChar)
    {
        cout << op << " ";
    }
    cout << endl;
    for (int i = 0; i < rowNum; i++)
    {
        for (int j = 0; j < colNum; j++)
        {
            cout << dfaTable[i][j] << " ";
        }
        cout << endl;
    }
}

void DisplaySimplifyDFA()
{
    int rowNum = SimplifyDFACounter;
    int colNum = operatorChar.size() + 2;

    for (auto sdfa : SDFAMap)
    {
        int num = sdfa.first;
        sdfaTable[num][1] = intToString(num);
        SimplifyDFANode *sdfaNode = sdfa.second;
        if (sdfaNode->isAccepting)
            sdfaTable[num][0] = "+";
        if (sdfaNode->isStarting)
            sdfaTable[num][0] += "-";

        int col = 2;
        for (auto op : operatorChar)
        {
            for (int i = 0; i < sdfaNode->transitions.size(); i++)
            {
                if (sdfaNode->transitions[i].first == op)
                {
                    sdfaTable[num][col] += intToString(sdfaNode->transitions[i].second->id);
                }
            }
            col++;
        }
    }

    for (int i = 0; i < rowNum; i++)
    {
        for (int j = 0; j < colNum; j++)
        {
            if (sdfaTable[i][j] == "")
                sdfaTable[i][j] = " ";
        }
    }

    cout << "     ";
    for (auto op : operatorChar)
    {
        cout << op << "  ";
    }
    cout << endl;
    for (int i = 0; i < rowNum; i++)
    {
        for (int j = 0; j < colNum; j++)
        {
            cout << sdfaTable[i][j] << " ";
        }
        cout << endl;
    }
}

void calculateDegree()
{
    for (int i = 1; i <= stateCounter; i++)
    {
        outDegree[i] += G[i].size();
        for (int j = 0; j < G[i].size(); j++)
        {
            inDegree[G[i][j]->id]++;
        }
    }
}

// 在图形场景中绘制一个状态，包括其外观（圆形）和可能的状态属性（是否是起始状态或接受状态）
void parsing::drawState(QGraphicsScene *scene, int x, int y, QString label, bool isStart, bool isAccept)
{
    // 使用白色填充圆圈 蓝色表示开始 红色外弧表示状态 白色内部填充
    QPen blackPen(Qt::black);
    QPen bluePen(Qt::blue);
    QPen redPen(Qt::red);
    QBrush whiteBrush(Qt::white);

    // 画状态圆圈 椭圆 设置东西南北半径为相同=>圆  前两个参数是矩形的左上角位置坐标 后两个为矩形的宽度和高度
    QGraphicsEllipseItem *circle = scene->addEllipse(x - 25, y - 25, 50, 50, blackPen, whiteBrush);

    // 如果是接受状态，画红色双圆
    if (isAccept)                       
    {
        // 圆心的坐标是 (x, y)，但是为了确保圆形的边界对齐到 (x, y)
        scene->addEllipse(x - 30, y - 30, 60, 60, redPen);
    }

    // 如果是开始状态，画蓝色空心箭头
    if (isStart)
    {
        // 创建箭头轮廓的多边形
        QPolygonF arrowOutline;
        arrowOutline << QPointF(x - 60, y - 10)  // 左上
                     << QPointF(x - 35, y - 10)  // 右上
                     << QPointF(x - 35, y - 15)  // 箭头尖上部
                     << QPointF(x - 25, y)       // 箭头尖
                     << QPointF(x - 35, y + 15)  // 箭头尖下部
                     << QPointF(x - 35, y + 10)  // 右下
                     << QPointF(x - 60, y + 10); // 左下

        // 使用白色填充，蓝色边框
        scene->addPolygon(arrowOutline, bluePen, whiteBrush);
    }

    // 创建一个文本项，显示状态标签（label），并将文本居中对齐到状态圆圈中
    // 添加状态标签，使用黑色文字
    QGraphicsTextItem *text = scene->addText(label);
    text->setDefaultTextColor(Qt::black);
    // 调整文字位置，使其居中显示
    QRectF textRect = text->boundingRect();
    // 文本框的左上角应该放置的坐标 本项居中显示在 (x, y) 位置
    text->setPos(x - textRect.width() / 2, y - textRect.height() / 2);
}

// 绘制从一个状态到另一个状态的转移，支持普通转移和自环转移
void parsing::drawTransition(QGraphicsScene *scene, QPointF start, QPointF end, QString label)
{
    QPen pen(Qt::black);
    double stateRadius = 25; // 状态圆的半径

    // 判断是否是自环
    if (start == end)
    {
        QPainterPath path;
        // 在 Qt 和大多数计算机图形学系统中，坐标系的 原点 ((0, 0)) 通常位于左上角，因此：
        //         x 坐标：向右增大。
        //         y 坐标：向下增大。
        //         所以，y 坐标的增大表示在垂直方向上向 下 移动，而减少表示向 上 移动。
        // 控制点，用于创建更自然的曲线 start.y() - 25纵坐标向上偏移 25 个单位
        QPointF startPoint(start.x(), start.y() - 25);         // 起点 连接的不是圆心 而是圆上
        QPointF controlPoint1(start.x() - 40, start.y() - 60); // 第一个控制点
        QPointF controlPoint2(start.x() + 40, start.y() - 60); // 第二个控制点
        QPointF endPoint(start.x() + 5, start.y() - 25);       // 终点

        // 绘制三次贝塞尔曲线
        // 移动到起始点，将会开始一个新路径，关闭上一个子路径
        path.moveTo(startPoint);
        // 函数原型：void QPainterPath::​cubicTo(const QPointF & c1, const QPointF & c2, const QPointF & endPoint)
        // 使用C1和C2指定的控制点在当前位置和给定端点之间添加三次贝塞尔曲线，添加曲线后，当前位置将更新为曲线的终点
        path.cubicTo(controlPoint1, controlPoint2, endPoint);
        scene->addPath(path, pen);

        // 添加箭头
        double angle = -0.5; // 箭头角度 第一象限 固定 因为是自环
        QPointF arrowP1 = endPoint + QPointF(cos(angle - M_PI / 6) * 10,
                                             sin(angle - M_PI / 6) * 10);
        QPointF arrowP2 = endPoint + QPointF(cos(angle + M_PI / 6) * 10,
                                             sin(angle + M_PI / 6) * 10);

        QPolygonF arrow;
        // 计算箭头的两个端点，并绘制一个箭头指向转移的终点
        arrow << endPoint << arrowP1 << arrowP2;
        scene->addPolygon(arrow, pen, QBrush(Qt::black));

        // 添加标签 设置在自环的上方
        QGraphicsTextItem *text = scene->addText(label);
        text->setDefaultTextColor(Qt::black);
        QRectF textRect = text->boundingRect();
        text->setPos(start.x() - textRect.width() / 2, start.y() - 72);
    }
    else
    {
        QPainterPath path;

        // 计算两点之间的向量
        QLineF line(start, end);
        // 该向量与水平方向的夹角 并将其转换为弧度
        double angle = line.angle() * M_PI / 180.0;

        // 计算起点和终点（在圆的边缘） 即将两个点连接起来后与圆上的交点
        QPointF adjustedStart(start.x() + stateRadius * cos(angle),
                              start.y() - stateRadius * sin(angle));
        QPointF adjustedEnd(end.x() - stateRadius * cos(angle),
                            end.y() + stateRadius * sin(angle));

        // 计算控制点
        QPointF midPoint = (adjustedStart + adjustedEnd) / 2;
        double normalAngle = line.angle() + 90;
        double offset = 30.0; // 控制曲线的弯曲程度
        // 二次贝塞尔曲线 控制点的位置是起点和终点之间的中点，并根据法线角度（即向量垂直方向）向外偏移一定的距离来使曲线弯曲
        QPointF controlPoint = midPoint + QPointF(
                                              cos(normalAngle * M_PI / 180.0) * offset,
                                              -sin(normalAngle * M_PI / 180.0) * offset);

        // 绘制二次贝塞尔曲线 计算起始和终止状态的圆边缘位置，然后通过控制点绘制平滑的曲线
        path.moveTo(adjustedStart);
        path.quadTo(controlPoint, adjustedEnd);
        scene->addPath(path, pen);

        // 计算箭头方向 从控制点到终点的向量 指向箭头的方向
        QPointF tangentVector = adjustedEnd - controlPoint;
        // 计算向量与水平方向的夹角
        double arrowAngle = atan2(tangentVector.y(), tangentVector.x());

        // 添加箭头
        double arrowSize = 8.0;
        // arrowP1 和 arrowP2 是箭头的左右两个分支 偏离主方向30度
        QPointF arrowP1 = adjustedEnd + QPointF(
                                            cos(arrowAngle + M_PI - M_PI / 6) * arrowSize,
                                            sin(arrowAngle + M_PI - M_PI / 6) * arrowSize);
        QPointF arrowP2 = adjustedEnd + QPointF(
                                            cos(arrowAngle + M_PI + M_PI / 6) * arrowSize,
                                            sin(arrowAngle + M_PI + M_PI / 6) * arrowSize);

        QPolygonF arrow;
        // 计算并绘制箭头，指向转移的终点  arrow << 将点依次添加到 QPolygonF 的内部点集合中
        arrow << adjustedEnd << arrowP1 << arrowP2;
        scene->addPolygon(arrow, pen, QBrush(Qt::black));

        // 添加标签
        QGraphicsTextItem *text = scene->addText(label);
        text->setDefaultTextColor(Qt::black);
        QRectF textRect = text->boundingRect();

        // 将标签放在控制点附近
        double labelOffset = 15.0;
        QPointF labelPos = controlPoint + QPointF(
                                              cos(normalAngle * M_PI / 180.0) * labelOffset,
                                              -sin(normalAngle * M_PI / 180.0) * labelOffset);

        text->setPos(labelPos.x() - textRect.width() / 2,
                     labelPos.y() - textRect.height() / 2);
    }
}

void parsing::drawDFAGraph(bool isMinimized)
{
    // 隐藏可能占用相同位置的控件
    ui->textBrowser->hide();
    ui->tableWidget->hide();
    ui->graphWidget->show();
    // view scene已经在prasing.h中定义
    
    // 清除之前的视图
    // view 是 QGraphicsView 对象，用于显示图形视图
    // scene 是 QGraphicsScene 对象，用于存放所有图形项（例如状态、转移）
    if (view)
    {
        // graphLayout类比textBrowser  tableWidget 是一个画布
        ui->graphLayout->removeWidget(view);
        delete view;
    }
    if (scene)
    {
        delete scene;
    }

    scene = new QGraphicsScene(this);
    // view必须在scene的基础上创建
    view = new QGraphicsView(scene);

    // 设置视图大小
    view->setMinimumSize(600, 400);

    // 圆形布局，将状态均匀分布在一个圆周上
    int radius = 150;
    int centerX = 300;
    int centerY = 200;
    // 存储每个状态的Id与坐标（x,y）=><int, QPointF>
    std::map<int, QPointF> statePositions;

    // 用于存储边的标签 Id与Id间的转换符号 =><pair<int, int>, QString>
    map<pair<int, int>, QString> edgeLabels;

    if (isMinimized)
    {
        // 处理最小化DFA
        int numStates = SDFAMap.size();
        int i = 0;
        // 根据状态的索引 i 和状态总数 numStates 来计算角度 angle，再利用三角函数计算坐标 (x, y)
        // 将状态均匀分布在一个圆周上
        for (auto &state : SDFAMap)
        {
            // 从正 x 轴（右方向）开始，逆时针方向增加
            double angle = 2 * M_PI * i / numStates;
            int x = centerX + radius * cos(angle);
            int y = centerY + radius * sin(angle);

            QString label = QString::number(state.first);
            bool isStart = state.second->isStarting;
            bool isAccept = state.second->isAccepting;

            drawState(scene, x, y, label, isStart, isAccept);
            // 每个Id所对应的SDFA都有一个状态 statePositions存储的是节点的ID与QPoint的映射
            statePositions[state.first] = QPointF(x, y);
            i++;
        }

        // 收集所有转换的标签
        for (auto &state : SDFAMap)
        {
            for (auto &trans : state.second->transitions)
            {
                int fromState = state.first;
                int toState = trans.second->id;
                // 转换符号
                QString symbol(trans.first);

                auto key = make_pair(fromState, toState);
                if (edgeLabels.find(key) == edgeLabels.end())
                {
                    edgeLabels[key] = symbol;
                }
                else
                {
                    edgeLabels[key] += "," + symbol;
                }
            }
        }

        // 画出所有转换
        for (const auto &edge : edgeLabels)
        {
            // statePositions存储的是节点的ID与与QPoint的映射
            QPointF start = statePositions[edge.first.first];
            QPointF end = statePositions[edge.first.second];
            drawTransition(scene, start, end, edge.second);
        }
    }
    else
    {
        // 处理普通DFA
        int numStates = dfaNodes.size();
        int i = 0;
        for (auto &state : dfaNodes)
        {
            double angle = 2 * M_PI * i / numStates;
            int x = centerX + radius * cos(angle);
            int y = centerY + radius * sin(angle);

            QString label = QString::number(state->id);
            bool isStart = state->isStarting;
            bool isAccept = state->isAccepting;

            drawState(scene, x, y, label, isStart, isAccept);
            statePositions[state->id] = QPointF(x, y);
            i++;
        }

        // 收集所有转换的标签
        for (auto &state : dfaNodes)
        {
            for (auto &trans : state->transitions)
            {
                int fromState = state->id;
                int toState = trans.second->id;
                QString symbol(trans.first);

                auto key = make_pair(fromState, toState);
                if (edgeLabels.find(key) == edgeLabels.end())
                {
                    edgeLabels[key] = symbol;
                }
                else
                {
                    edgeLabels[key] += "," + symbol;
                }
            }
        }

        // 画出所有转换
        for (const auto &edge : edgeLabels)
        {
            QPointF start = statePositions[edge.first.first];
            QPointF end = statePositions[edge.first.second];
            drawTransition(scene, start, end, edge.second);
        }
    }

    // 添加视图到布局
    ui->graphLayout->addWidget(view);
}

void parsing::on_startAnalysis_clicked() // 开始分析
{

    stateCounter = 0;
    DFANodeCounter = 0;
    SimplifyDFACounter = 0;
    priorityMap.clear();
    operatorChar.clear();
    operatorCharTmp.clear();
    dfaNodes.clear();
    for (int i = 0; i < 1000; i++)
    {
        G[i].clear();
    }
    for (int i = 0; i < 1000; i++)
    {
        DFAG[i].clear();
    }
    for (int i = 0; i < 1000; i++)
    {
        SDFAG[i].clear();
    }
    for (int i = 0; i < 1000; i++)
    {
        outDegree[i] = 0;
        inDegree[i] = 0;
    }

    NFAMap.clear();
    SDFAMap.clear();
    for (int i = 0; i < 1000; i++)
    {
        for (int j = 0; j < 1000; j++)
        {
            nfaTable[i][j] = "";
            dfaTable[i][j] = "";
            sdfaTable[i][j] = "";
        }
    }



    // 设置优先级 并没有为()设置优先级
    priorityMap.insert(make_pair('*', 3));
    priorityMap.insert(make_pair('+', 3));
    priorityMap.insert(make_pair('.', 2));
    priorityMap.insert(make_pair('|', 1));

    string regex;
    QString text = ui->expressionText->toPlainText(); // 获取编辑框的全部文本
    regex = text.toStdString();                       // 将QString对象转换为std::string对象
    // 不是最后一个换行 就当做或处理
    for (int i = 0; i < regex.size(); i++)
    {
        if (regex[i] == '\n' && i != regex.size() - 1)
            regex[i] = '|';
    }
    cout << regex << endl;
    // 只有c1不是( | 且c2不是) | + * 时 才在中间加.
    // only supply ()+*|以及.
    for (int i = 0; i < regex.size() - 1; i++)
    {
        if (isWordChar(regex[i]) && isWordChar(regex[i + 1]) || isWordChar(regex[i]) && regex[i + 1] == '(' || regex[i] == ')' && isWordChar(regex[i + 1]) || regex[i] == '*' && regex[i + 1] != ')' && regex[i + 1] != '|' && regex[i + 1] != '+' && regex[i + 1] != '*' || regex[i] == '+' && regex[i + 1] != ')' && regex[i + 1] != '|' && regex[i + 1] != '+' && regex[i + 1] != '*' || regex[i] == ')' && regex[i + 1] == '(')
        {
            string str1 = regex.substr(0, i + 1);
            string str2 = regex.substr(i + 1, (regex.size() - i));
            str1 += ".";
            regex = str1 + str2;
        }
    }
    cout << regex << endl;
    // 将正则表达式转换为NFA时 ε转换出度入度不会-- 而非ε转换出度入度会--
    // 然后执行的是计算度数函数 将ε转换与非ε转换的出度入度均++
    // 故最后再NFA转DFA时 使用出度入度<=0判断的是 ：是否为ε转换
    // 如果是ε转换 则不满足条件 不执行
    // 故最后出度入度<=0的点均为非ε转换的点
    bool nfa = regexToNFA(regex);

    if(nfa)
    {
        // 清空完毕
        QFont font;
        font.setPointSize(16);
        ui->textBrowser->setFont(font);
        ui->textBrowser->show();
        ui->textBrowser->setText("Analysis successfully, please click other buttons to achieve different functions.");
        ui->tableWidget->close();
        ui->graphWidget->hide();
        calculateDegree();
        NFAtoDFA();
        SimplifyDFA();
        BuildSimplifyDFA();

        cout << " ------------- 开始输出 NFA 表--------------" << endl;
        DisplayNFA();
        cout << " ------------- 开始输出 DFA 表--------------" << endl;
        DisplayDFA();
        cout << " ------------- 开始输出化简后的 DFA 表--------------" << endl;
        DisplaySimplifyDFA();
    }
    else
    {
        // 清空完毕
        QFont font;
        font.setPointSize(16);
        ui->textBrowser->setFont(font);
        ui->textBrowser->show();
        ui->textBrowser->setText("Analysis failed, please check error.");
        ui->tableWidget->close();
        ui->graphWidget->hide();
    }
}

void parsing::on_printNFA_clicked() // NFA
{
    ui->graphWidget->hide();
    ui->textBrowser->hide();
    ui->tableWidget->show();
    int rowNum = stateCounter;
    int colNum = operatorCharTmp.size() + 2;
    ui->tableWidget->setRowCount(rowNum + 1);
    ui->tableWidget->setColumnCount(colNum);
    QFont Font;
    Font.setPointSize(15);
    ui->tableWidget->setFont(Font);
    ui->tableWidget->setItem(0, 0, new QTableWidgetItem("Start/End Tag"));
    ui->tableWidget->setItem(0, 1, new QTableWidgetItem("Vertex\\Edge"));
    int temp = 2;
    for (auto op : operatorCharTmp)
    {
        ui->tableWidget->setItem(0, temp, new QTableWidgetItem(QString(op)));
        temp++;
    }
    // 循环COUNTER次
    for (int i = 1; i < rowNum + 1; i++)
    {
        for (int j = 0; j < colNum; j++)
        {
            // nfaTable第i行的数据要放在tableWidget的第i+1行
            ui->tableWidget->setItem(i, j, new QTableWidgetItem(QString::fromStdString(nfaTable[i - 1][j])));
        }
    }
    ui->tableWidget->resizeColumnsToContents();
    ui->tableWidget->resizeRowsToContents();
}

void parsing::on_printDFA_clicked() // DFA
{
    ui->graphWidget->hide();
    ui->textBrowser->hide();
    ui->tableWidget->show();
    int rowNum = DFANodeCounter;
    int colNum = operatorChar.size() + 2;
    ui->tableWidget->setRowCount(rowNum + 1);
    ui->tableWidget->setColumnCount(colNum);
    QFont Font;
    Font.setPointSize(15);
    ui->tableWidget->setFont(Font);
    ui->tableWidget->setItem(0, 0, new QTableWidgetItem("Start/End Tag"));
    ui->tableWidget->setItem(0, 1, new QTableWidgetItem("Vertex\\Edge"));
    int temp = 2;
    for (auto op : operatorChar)
    {
        ui->tableWidget->setItem(0, temp, new QTableWidgetItem(QString(op)));
        temp++;
    }
    // 循环COUNTER次
    for (int i = 1; i < rowNum + 1; i++)
    {
        for (int j = 0; j < colNum; j++)
        {
            // dfaTable第i行的数据要放在tableWidget的第i+1行
            ui->tableWidget->setItem(i, j, new QTableWidgetItem(QString::fromStdString(dfaTable[i - 1][j])));
        }
    }
    ui->tableWidget->resizeColumnsToContents();
    ui->tableWidget->resizeRowsToContents();
}

void parsing::on_minimizeDFA_clicked() // 最小化NFA
{
    ui->graphWidget->hide();
    ui->textBrowser->hide();
    ui->tableWidget->show();
    int rowNum = SimplifyDFACounter;
    int colNum = operatorChar.size() + 2;
    ui->tableWidget->setRowCount(rowNum + 1);
    ui->tableWidget->setColumnCount(colNum);
    QFont Font;
    Font.setPointSize(15);
    ui->tableWidget->setFont(Font);
    ui->tableWidget->setItem(0, 0, new QTableWidgetItem("Start/End Tag"));
    ui->tableWidget->setItem(0, 1, new QTableWidgetItem("Vertex\\Edge"));
    int temp = 2;
    for (auto op : operatorChar)
    {
        ui->tableWidget->setItem(0, temp, new QTableWidgetItem(QString(op)));
        temp++;
    }
    // 循环COUNTER次
    for (int i = 1; i < rowNum + 1; i++)
    {
        for (int j = 0; j < colNum; j++)
        {
            // sdfaTable第i行的数据要放在tableWidget的第i+1行
            ui->tableWidget->setItem(i, j, new QTableWidgetItem(QString::fromStdString(sdfaTable[i - 1][j])));
        }
    }
    ui->tableWidget->resizeColumnsToContents();
    ui->tableWidget->resizeRowsToContents();
}

void parsing::on_saveAsFile_clicked()
{
    QString text = ui->expressionText->toPlainText();
    string regex = text.toStdString();

    // 使用文件对话框让用户选择保存的文件位置和文件名
    QString saveFilePath = QFileDialog::getSaveFileName(
        this,
        "保存正则表达式文件",
        "C:/Users/dell/Desktop/NFA-DFA/test_lexical_expression/regex.txt", // 默认文件路径
        "文本文件 (*.txt);;所有文件 (*.*)"
        );

    // 检查用户是否选择了有效的文件路径
    if (!saveFilePath.isEmpty())
    {
        // 打开一个文件流用于保存文件
        ofstream outputFile(saveFilePath.toStdString());

        // 检查文件是否成功打开
        if (outputFile.is_open())
        {
            // 写入内容到文件
            outputFile << regex;

            // 关闭文件流
            outputFile.close();

            // 提示用户文件保存成功
            QMessageBox::information(this, "保存成功", "文件已成功保存到: " + saveFilePath);
        }
        else
        {
            // 如果无法保存文件，弹出错误提示框
            QMessageBox::critical(this, "保存失败", "无法保存文件: " + saveFilePath);
        }
    }
}


void parsing::on_openFile_clicked()
{
    // 打开文件选择对话框以获取用户选择的文件 C:\\Users\\dell\\Desktop\\NFA-DFA\\test_lexical_expression
    QString filePath = QFileDialog::getOpenFileName(this, "请选择正则表达式文件", "C:\\Users\\dell\\Desktop\\NFA-DFA\\test_lexical_expression", "文本文件 (*.txt);;所有文件 (*.*)");

    // 检查用户是否取消了文件选择
    if (filePath.isEmpty())
    {
        return;
    }

    // 打开选择的文件
    QFile file(filePath);

    // 检查文件是否成功打开 以只读模式打开文本文件
    if (!file.open(QIODevice::ReadOnly | QIODevice::Text))
    {
        QMessageBox::critical(this, "错误", "无法打开文件");
        return;
    }

    // 创建文本流来读取文件内容
    QTextStream in(&file);

    // 读取文件中的文本到一个QString
    QString fileContents = in.readAll();

    // 关闭文件
    file.close();
    // 在这里，fileContents 包含了文件的文本内容，你可以对它进行操作，例如显示在UI上或者进行其他处理
    // 将文本内容显示在一个文本编辑框中：
    ui->expressionText->setPlainText(fileContents);
}

void parsing::on_showDFAGraph_clicked()
{
    drawDFAGraph(false); // 显示DFA图
}

void parsing::on_showMinDFAGraph_clicked()
{
    drawDFAGraph(true); // 显示最小化DFA图
}
